\chapter{上下文无关语言}

\section{上下文无关文法}

\subsection{上下文无关文法（CFG, Context Free Grammar）}

CFG能够描述某些具有递归结构的特征，它有足够强的语言表达力来表示大多数编程语言的语法。\\

CFG由一个四元组$ (V, T, P, S) $表示：

\begin{itemize}
    \item $ V $：变元（variable）/非终结符（non-terminal）集合，用大写字母表示。
    \item $ T $：终结符（terminal）集合，用小写字母表示。
    \item $ P $：产生式（production）集合。
    \item $ S $：开始符号。
\end{itemize}

\vspace{0.5cm}

一个文法由一组替换规则产生。产生式集合

\vspace{-1cm}

\begin{align*}
    A & \rightarrow \alpha_1 \\
    A & \rightarrow \alpha_2 \\
      & \cdots               \\
    A & \rightarrow \alpha_k
\end{align*}

可以被写成$ A \rightarrow \alpha_1\ |\ \alpha_2\ |\ \cdots\ |\ \alpha_k\ $的形式。\\

\subsection{推导（Derivation）}

推导用于确定符合文法规则的串的集合，即用来确定一个语言。\\

推导从开始符号开始，通过产生式进行替换，得到最终结果。\\

例如$ E \rightarrow E + E\ |\ E * E\ |\ (E)\ |\ id $，由开始符号$ E $可以推导出$ (id + id) * id $。

\vspace{-1cm}

\begin{align*}
    E & \Rightarrow E * E          \\
      & \Rightarrow (E) * E        \\
      & \Rightarrow (E) * id       \\
      & \Rightarrow (E + E) * id   \\
      & \Rightarrow (E + id) * id  \\
      & \Rightarrow (id + id) * id
\end{align*}

解析树（parse tree）是描述推导的一种直观方法。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            -,
            level distance=1.5cm,
            level 1/.style={sibling distance=4cm},
            level 2/.style={sibling distance=3cm},
            level 3/.style={sibling distance=2cm},
            level 4/.style={sibling distance=1cm}
        ]
        \node {$ E $}
        child {
                node {$ E $}
                child {
                        node {$ ( $}
                    }
                child {
                        node {$ E $}
                        child {
                                node {$ E $}
                                child {
                                        node {$ id $}
                                    }
                            }
                        child {
                                node {$ + $}
                            }
                        child {
                                node {$ E $}
                                child {
                                        node {$ id $}
                                    }
                            }
                    }
                child {
                        node {$ ) $}
                    }
            }
        child {
                node {$ * $}
            }
        child {
                node {$ E $}
                child {
                        node {$ id $}
                    }
            };
    \end{tikzpicture}
    \caption{分析树}
\end{figure}

\vspace{0.5cm}

如果只关注语义分析和代码生成所需的信息，可以将分析树简化为一棵抽象语法树（abstract syntex tree）。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            -,
            level distance=1.5cm,
            level 1/.style={sibling distance=3cm},
            level 2/.style={sibling distance=2cm},
            level 3/.style={sibling distance=2cm}
        ]
        \node {$ * $}
        child {
                node {$ + $}
                child {
                        node {$ id $}
                    }
                child {
                        node {$ id $}
                    }
            }
        child {
                node {$ id $}
            };
    \end{tikzpicture}
    \caption{抽象语法树}
\end{figure}

\vspace{0.5cm}

\subsection{二义性（Ambiguity）}

在推导的过程中涉及到同级别表达式的替换，因此按顺序可以分为最左推导（leftmost derivation）和最右推导（rightmost derivation）。\\

文法的二义性，是指对于符合文法规则的同一个句子，存在两种可能的分析树。\\

例如$ E \rightarrow E + E\ |\ E * E\ |\ (E)\ |\ x\ |\ y\ |\ z $，使用最左推导会对$ x + y * z $产生两个不同的分析树。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            -,
            level distance=1.5cm,
            level 1/.style={sibling distance=3cm},
            level 2/.style={sibling distance=2cm},
            level 3/.style={sibling distance=2cm}
        ]
        \node {$ E $}
        child {
                node {$ E $}
                child {
                        node {$ x $}
                    }
            }
        child {
                node {$ + $}
            }
        child {
                node {$ E $}
                child {
                        node {$ y $}
                    }
                child {
                        node {$ * $}
                    }
                child {
                        node {$ z $}
                    }
            };
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            -,
            level distance=1.5cm,
            level 1/.style={sibling distance=3cm},
            level 2/.style={sibling distance=2cm},
            level 3/.style={sibling distance=2cm}
        ]
        \node {$ E $}
        child {
                node {$ E $}
                child {
                        node {$ x $}
                    }
                child {
                        node {$ + $}
                    }
                child {
                        node {$ y $}
                    }
            }
        child {
                node {$ * $}
            }
        child {
                node {$ E $}
                child {
                        node {$ z $}
                    }
            };
    \end{tikzpicture}
\end{figure}

\vspace{0.5cm}

产生二义性的原因在于运算符之间的优先级在文法中并没有体现。消除二义性的办法就是在文法中引入一个中间量。

\vspace{-1cm}

\begin{align*}
    E & \rightarrow E + T\ |\ T \\
    T & \rightarrow T * F\ |\ F \\
    F & \rightarrow id\ |\ (E)
\end{align*}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[
            -,
            level distance=1.5cm,
            level 1/.style={sibling distance=3cm},
            level 2/.style={sibling distance=2cm},
            level 3/.style={sibling distance=2cm}
        ]
        \node {$ E $}
        child {
                node {$ E $}
                child {
                        node {$ T $}
                        child {
                                node {$ F $}
                                child {
                                        node {$ x $}
                                    }
                            }
                    }
            }
        child {
                node {$ + $}
            }
        child {
                node {$ T $}
                child {
                        node {$ T $}
                        child {
                                node {$ F $}
                                child {
                                        node {$ y $}
                                    }
                            }
                    }
                child {
                        node {$ * $}
                    }
                child {
                        node {$ F $}
                        child {
                                node {$ z $}
                            }
                    }
            };
    \end{tikzpicture}
\end{figure}

\newpage

\section{CNF}

\subsection{上下文无关语言}

CFG可以用来表示语言$ \{a^nb^n\ |\ n \ge 0\} $：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow aSb \\
    S & \rightarrow ab
\end{align*}

例如根据$ S $可以生成生成aaabbb：

\vspace{-1cm}

\begin{align*}
    S & \Rightarrow aSb    \\
      & \Rightarrow aaSbb  \\
      & \Rightarrow aaabbb
\end{align*}

CFG好还可以用于表示$ a $和$ b $出现相等次数的语言，例如babaab：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow aB\ |\ bA        \\
    A & \rightarrow a\ |\ aS\ |\ bAA \\
    B & \rightarrow b\ |\ bS\ |\ aBB
\end{align*}

设计CFG需要一定的创造力，大部分复杂的CFG可以由多个简单的CFG并集组成。\\

例如设计一个能够表示语言$ \{0^n1^n\ |\ n \ge 0\} \cup \{1^n0^n\ |\ n \ge 0\} $的CFG。\\

这两个部分可以分别表示为：

\vspace{-1cm}

\begin{align*}
    S_1 & \rightarrow 0S_{1}1\ |\ \epsilon \\
    S_2 & \rightarrow 1S_{2}0\ |\ \epsilon
\end{align*}

只需合并这两个部分，即可得到最终的CFG：

\vspace{-1cm}

\begin{align*}
    S   & \rightarrow S_1\ |\ S_2          \\
    S_1 & \rightarrow 0S_{1}1\ |\ \epsilon \\
    S_2 & \rightarrow 1S_{2}0\ |\ \epsilon
\end{align*}

\vspace{0.5cm}

\subsection{乔姆斯基范式（CNF, Chomsky Normal Form）}

CNF在保留相同语言的同时对语法规则施加了一些限制，好处是可以避免解析过程中的歧义问题，另一个好处就是为解析的复杂度提供了一个上限。\\

CNF规定每条CFG的每一条规则都必须满足：

\begin{enumerate}
    \item $ S \rightarrow \epsilon $：开始变元$ S $可以为空。
    \item $ A \rightarrow BC $：单个变元可以推导出两个变元，其中$ B $、$ C $不能为开始变元。
    \item $ A \rightarrow a $：单个变元可以被终结符替换。
    \item 不能出现单个变元推导出单个变元。
\end{enumerate}

\vspace{0.5cm}

将CFG转换为CNF的步骤为：

\begin{enumerate}
    \item 添加新的开始变元：确保开始变元始终在规则的左侧。
    \item 消除所有$ \epsilon $规则：消除从变元到空字符的规则。
    \item 消除所有$ A \rightarrow B $规则：消除单个变元到单个变元的规则。
    \item 添加变元：为了满足$ A \rightarrow BC $的规则，需要将$ A \rightarrow BCD $替换为$ A \rightarrow ED $，即添加变元$ E \rightarrow BC $。
\end{enumerate}

\vspace{0.5cm}

例如将CFG转换为CNF：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow ABA             \\
    A & \rightarrow aA\ |\ \epsilon \\
    B & \rightarrow bB\ |\ \epsilon
\end{align*}

\subsubsection{消除所有$ \epsilon $规则}

将$ A \rightarrow \epsilon $的规则，替换到出现$ A $的规则中：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow ABA\ |\ \textcolor{red}{BA\ |\ AB\ |\ B} \\
    A & \rightarrow aA\ |\ \textcolor{red}{a}                \\
    B & \rightarrow bB\ |\ \epsilon
\end{align*}

将$ B \rightarrow \epsilon $的规则，替换到出现$ B $的规则中：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow ABA\ |\ BA\ |\ AB\ |\ B\ |\ \textcolor{red}{AA\ |\ A} \\
    A & \rightarrow aA\ |\ a                                              \\
    B & \rightarrow bB\ |\ \textcolor{red}{b}
\end{align*}

\subsubsection{消除所有$ A \rightarrow B $规则}

在$ S $中出现了单个变元到单个变元的情况，将这些规则进一步替换：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow ABA\ |\ BA\ |\ AB\ |\ \textcolor{red}{bB\ |\ b}\ |\ AA\ |\ \textcolor{red}{aA\ |\ a} \\
    A & \rightarrow aA\ |\ a                                                                             \\
    B & \rightarrow bB\ |\ b
\end{align*}

目前，$ S \rightarrow BA $、$ S \rightarrow AA $、$ S \rightarrow AB $、$ S \rightarrow a $、$ S \rightarrow b $、$ A \rightarrow a $、$ B \rightarrow b $这些规则已经满足了CNF的要求：

\vspace{-1cm}

\begin{align*}
    S & \rightarrow ABA\ |\ \textcolor{ForestGreen}{BA\ |\ AB}\ |\ bB\ |\ \textcolor{ForestGreen}{b\ |\ AA}\ |\ aA\ |\ \textcolor{ForestGreen}{a} \\
    A & \rightarrow aA\ |\ \textcolor{ForestGreen}{a}                                                                                             \\
    B & \rightarrow bB\ |\ \textcolor{ForestGreen}{b}
\end{align*}

\subsubsection{添加变元}

为了消除$ A \rightarrow BCD $这种情况，需要添加新的变元进行替换。\\

假设$ X \rightarrow AB $：

\vspace{-1cm}

\begin{align*}
    S                  & \rightarrow \textcolor{red}{XA}\ |\ \textcolor{ForestGreen}{BA\ |\ AB}\ |\ bB\ |\ \textcolor{ForestGreen}{b\ |\ AA}\ |\ aA\ |\ \textcolor{ForestGreen}{a} \\
    A                  & \rightarrow aA\ |\ \textcolor{ForestGreen}{a}                                                                                                             \\
    B                  & \rightarrow bB\ |\ \textcolor{ForestGreen}{b}                                                                                                             \\
    \textcolor{red}{X} & \textcolor{red}{\rightarrow} \textcolor{red}{AB}
\end{align*}

同时为了满足CNF规则中$ A \rightarrow BC $的要求，需要对如$ A \rightarrow aA $这样的规则进行替换。\\

假设$ A_1 \rightarrow a $、$ B_1 \rightarrow b $：

\vspace{-1cm}

\begin{align*}
    S                    & \rightarrow \textcolor{ForestGreen}{XA\ |\ BA\ |\ AB}\ |\ \textcolor{red}{B_1B}\ |\ \textcolor{ForestGreen}{b\ |\ AA}\ |\ \textcolor{red}{A_1A}\ |\ \textcolor{ForestGreen}{a} \\
    A                    & \rightarrow \textcolor{red}{A_1A}\ |\ \textcolor{ForestGreen}{a}                                                                                                               \\
    B                    & \rightarrow \textcolor{red}{B_1B}\ |\ \textcolor{ForestGreen}{b}                                                                                                               \\
    X                    & \rightarrow \textcolor{ForestGreen}{AB}                                                                                                                                        \\
    \textcolor{red}{A_1} & \textcolor{red}{\rightarrow} \textcolor{red}{a}                                                                                                                                \\
    \textcolor{red}{B_1} & \textcolor{red}{\rightarrow} \textcolor{red}{b}
\end{align*}

这样就完成了CFG到CNF的转换，语法中的每条规则都满足了CNF的要求。

\newpage

\section{PDA}

\subsection{下推自动机（PDA, Pushdown Automata）}

DFA和NFA由于受限于存储空间的问题，不能识别类似于$ \{a^nb^n\ |\ n \ge 0\} $这种语言。PDA通过一个栈（stack）解决了这个问题。PDA与CFG的功能的等价的。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ a $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ b $};
        \node[draw] [on chain] {$ b $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ 0 $};
        \node[draw] [on chain] {$ x $};
        \node[draw] [on chain] {$ y $};
        \node[draw] [on chain] {$ z $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-1.east);
        \end{scope}
    \end{tikzpicture}
    \caption{PDA}
\end{figure}

PDA由一个六元组$ (Q, \Sigma, \Gamma, \delta, q_0, F) $表示：

\begin{itemize}
    \item $ Q $：状态集合
    \item $ \Sigma $：输入字母表
    \item $ \Gamma $：栈字母表
    \item $ \delta $：状态转移函数
    \item $ q_0 $：初始状态
    \item $ F $：终结状态集合
\end{itemize}

\vspace{0.5cm}

例如状态转移函数$ \delta(q_1, a, b) = \{(q_2, \epsilon)\} $表示，在状态$ q_1 $时，如果输入字符为$ a $，并且栈顶元素为$ b $，那么就将$ a $消耗掉，并将$ b $出栈，进入状态$ q_2 $。在PDA中可表示为$ a, b \rightarrow \epsilon $。\\

例如状态转移函数$ \delta(q_3, \epsilon, b) = \{(q_4, a), (q_5, b)\} $表示，在状态$ q_3 $时，如果输入字符为空，并且栈顶元素为$ b $，那么有两种选择：

\begin{enumerate}
    \item 使用$ a $代替栈顶元素$ b $，并进入状态$ q_4 $。
    \item 栈保持原样（$ b $为栈顶），并进入状态$ q_5 $。
\end{enumerate}

\vspace{0.5cm}

能够识别$ \{a^nb^n\ |\ n \ge 0\} $的PDA如下：

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \node[state, initial, accepting] (q0) {$ q_0 $};
        \node[state] (q1) at (4,0) {$ q_1 $};
        \node[state] (q2) at (4,-4) {$ q_2 $};
        \node[state, accepting] (q3) at (0,-4) {$ q_3 $};

        \draw (q0) edge[above] node{$ \epsilon, \epsilon \rightarrow \$ $} (q1)
        (q1) edge[loop above] node{$ a, \epsilon \rightarrow a $} (q1)
        (q1) edge[right] node{$ b, a \rightarrow \epsilon $} (q2)
        (q2) edge[loop right] node{$ b, a \rightarrow \epsilon $} (q2)
        (q2) edge[above] node{$ \epsilon, \$ \rightarrow \epsilon $} (q3);
    \end{tikzpicture}
    \caption{识别$ \{a^nb^n\ |\ n \ge 0\} $的PDA}
\end{figure}

识别串$ aabb $的过程如下：\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ a $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ b $};
        \node[draw] [on chain] {$ b $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ \$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-4.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ a $};
        \node[draw] [on chain] {$ b $};
        \node[draw] [on chain] {$ b $};
        \node[draw] [on chain] {$  $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ \$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-3.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ b $};
        \node[draw] [on chain] {$ b $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ \$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-2.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ b $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ a $};
        \node[draw] [on chain] {$ \$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-3.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ \$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-4.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=0mm, every node/.style={minimum size=8mm}]
        \node[draw] (deb) {State Control};

        { [start chain=1]
        \node[draw] [on chain] at (3,-2){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        }
        \node at (4.5,-3) {input};

        { [start chain=2 going below]
        \node[draw] [on chain] at (-2,-3){$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        \node[draw] [on chain] {$ $};
        }
        \node at (-2,-6.5) {stack};

        \begin{scope}[->,>=latex']
            \draw (deb.east) -| (1-1);
            \draw (deb.south) |- (2-4.east);
        \end{scope}
    \end{tikzpicture}
\end{figure}

\newpage

\section{预测分析法}

\subsection{LL(1)文法}

例如产生式$ A \rightarrow +T\ |\ -P $，当读到$ + $开头的串的时候，可以很直接地判断选择$ A \rightarrow +T $这个生成式；而读到$ - $开头的串的时候，可以直接判断选择$ A \rightarrow -P $这个生成式。\\

像这种根据第一个token就能得出选择哪个生成式的情况，就叫做预测分析法。\\

LL(1)文法表示只查看后面1个符号，来判断需要选择的生成式。LL(k)文法则表示根据后k个符号来决定生成式。\\

但是，如果文法是类似于$ A \rightarrow T\ |\ P $这样都以非终结符开头的话，一眼就很难判断。因此就需要知道，$ T $是如何展开的。如果$ T \rightarrow a\ |\ b $，$ P \rightarrow c\ |\ d $, 那当串以$ a $或$ b $开头时，显然需要选择$ A \rightarrow T $；而当串以$ c $或$ d $开头时，就应该选择$ A \rightarrow P $这个生成式。\\

\subsection{FIRST}

为了能够预测下一个生成式，就需要知道每个生成式能够产生的开始符号的集合，称为FIRST集合。$ FIRST(\alpha) $是一个记录所有能够由$ \alpha $推导出的出现在开头的终结字符的集合。\\

例如：

\vspace{-1cm}

\begin{align*}
    E  & \rightarrow TE'               \\
    E' & \rightarrow +TE'\ |\ \epsilon \\
    T  & \rightarrow FT'               \\
    T' & \rightarrow *FT'\ |\ \epsilon \\
    F  & \rightarrow  (E)\ |\ id       \\
\end{align*}

每个终结符的FIRST集合都是自己本身。

\vspace{-1cm}

\begin{align*}
    FIRST(id)       & = \{id\}       \\
    FIRST(*)        & = \{*\}        \\
    FIRST(+)        & = \{+\}        \\
    FIRST(\text{(}) & = \{\text{(}\} \\
    FIRST(\text{)}) & = \{\text{)}\}
\end{align*}

如果$ E \rightarrow T $，则应该把$ FIRST(T) $也加入到$ FIRST(E) $中。

\vspace{-1cm}

\begin{align*}
    FIRST(E') & = \{+, \epsilon\}             \\
    FIRST(T') & = \{*, \epsilon\}             \\
    FIRST(F)  & = \{\text{(}, id\}            \\
    FIRST(T)  & = FIRST(F) = \{\text{(}, id\} \\
    FIRST(E)  & = FIRST(T) = \{\text{(}, id\}
\end{align*}

\vspace{0.5cm}

\subsection{FOLLOW}

仅有FIRST集合还不够，例如：

\vspace{-1cm}

\begin{align*}
    A & \rightarrow     Tb\ |\ P      \\
    T & \rightarrow    \epsilon\ |\ a \\
    P & \rightarrow   c
\end{align*}

可以得出：

\vspace{-1cm}

\begin{align*}
    FIRST(T) & = \{\epsilon, a\} \\
    FIRST(P) & = \{c\}
\end{align*}

当遇到$ a $开头的串时，应该选择$ A \rightarrow Tb $；当遇到$ c $开头的串时，应该选择$ A \rightarrow P $。\\

但其实，由于$ \epsilon $在$ FIRST(T) $中，所以当遇到$ b $开头的串时，也应该选择$ A \rightarrow Tb $。\\

所以，为了特殊处理当一个非终结字符可以推出$ \epsilon $的情况，就需要知道它后面紧跟的是什么终结字符，这样的集合被称为FOLLOW集合。\\

FOLLOW集合的规则：

\begin{enumerate}
    \item 当$ S $为开始符号时，将结束标记$ \$ $添加到$ FOLLOW(S) $中。

    \item 如果存在$ A \rightarrow \alpha B \beta $，那么$ FIRST(B) $中除了$ \epsilon $外所有符号都在$ FOLLOW(B) $中。

    \item 如果存在$ A \rightarrow \alpha B $或$ A \rightarrow \alpha B \beta $且$ FIRST(B) $中包含$ \epsilon $，那么$ FOLLOW(A) $中的所有符号都在$ FOLLOW(B) $中。
\end{enumerate}

\newpage